from cmath import inf
from typing import List


class Solution:
    """
     方法： 使用动态规划求解最大利润
            f[j][0]表示完成j次交易且不持有股票的最大利润
            f[j][1]表示完成j-1次交易且持有股票的最大利润
            对于每个价格p:
            - 卖出股票: f[j][0] = max(f[j][0], f[j][1] + p)
            - 买入股票: f[j][1] = max(f[j][1], f[j-1][0] - p)
     
     Args:
         k: int - 最多允许完成的交易次数
         prices: List[int] - 股票每天的价格列表
     
     Returns:
         int: 最多k次交易能获得的最大利润
     
     Time: O(n*k) - n为价格数组长度，k为最大交易次数
     
     Space: O(k) - 需要2*(k+2)大小的数组存储动态规划状态
     """
    def maxProfit(self, k: int, prices: List[int]) -> int:
        f = [[-inf] * 2 for _ in range(k + 2)]
        for j in range(1, k + 2):
            f[j][0] = 0
        for p in prices:
            for j in range(k + 1, 0, -1):
                f[j][0] = max(f[j][0], f[j][1] + p)
                f[j][1] = max(f[j][1], f[j-1][0] - p)
        return f[k+1][0]